import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/10 17:04
 * @description 字符串hash的作用时将字符串单映射为整数，用来确定两个字符串是否相等，该数据结构使具有了O(1)获取具有区间hash，比较两个子字符串的能力。
 *
 * 字符串hash中采用多项式hash函数 f(x) = sum(s[i] * b^(l-i) (mod M)), 单个字符ASCII码值 <=127， 可以理解为 128进制数或更大， 这里一般取素数 131 或者 13131作为进制
 *
 * 如 abc = 97 * 131^2 + 98 * 131^1 + 99;
 * xyz = x^2 + y^1 + z
 *
 * 字符串哈希也称为 Rabin-Karp算法
 */
public class StringHash {
    /**
     * 看字符串长度而定
     */
    int n = (int) 1e5 + 10;
    /**
     * 素数
     */
    int P = 131;
    /**
     * h[i] 作为 Hash的前缀字符
     */
    long[] h;
    long[] p;

    public void setHAndP(String s) {
        h = new long[n];
        p = new long[n];
        p[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            h[i + 1] = h[i] * P + s.charAt(i);
            p[i + 1] = p[i] * P;
        }
    }

    /**
     * 计算子串s[i..j]的哈希值
     * @param i i
     * @param j j
     * @return long
     */
    public long getClosed(int i, int j) {
        return h[j + 1] - h[i] * p[j - i + 1];
    }
}
